Search Results

Documents authored by Babai, László

Document
DOI: 10.4230/LIPIcs.CCC.2021.41
Matrix Rigidity Depends on the Target Field

Authors: László Babai and Bohdan Kivva

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977). We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2-o(1) between strict and absolute rigidities. The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments. Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over 𝔽₂.
Cite as

László Babai and Bohdan Kivva. Matrix Rigidity Depends on the Target Field. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.CCC.2021.41,
  author =	{Babai, L\'{a}szl\'{o} and Kivva, Bohdan},
  title =	{{Matrix Rigidity Depends on the Target Field}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{41:1--41:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.41},
  URN =		{urn:nbn:de:0030-drops-143153},
  doi =		{10.4230/LIPIcs.CCC.2021.41},
  annote =	{Keywords: Matrix rigidity, field extension}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.29
List-Decoding Homomorphism Codes with Arbitrary Codomains

Authors: László Babai, Timothy J. F. Black, and Angela Wuu

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
The codewords of the homomorphism code aHom(G,H) are the affine homomorphisms between two finite groups, G and H, generalizing Hadamard codes. Following the work of Goldreich-Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to mindist, the minimum distance of the code. In particular, for the first time, we do not require either G or H to be solvable. Specifically, we demonstrate a poly(1/epsilon) bound on the list size, i. e., on the number of codewords within distance (mindist-epsilon) from any received word, when G is either abelian or an alternating group, and H is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case. The abelian vs. arbitrary result permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (the codomain is a symmetric group) under the restriction that the domain G=A_n is paired with codomain H=S_m satisfying m < 2^{n-1}/sqrt{n}. The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018). We introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list. A homomorphism extender applied to a list of certificates yields the desired list.
Cite as

László Babai, Timothy J. F. Black, and Angela Wuu. List-Decoding Homomorphism Codes with Arbitrary Codomains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.APPROX-RANDOM.2018.29,
  author =	{Babai, L\'{a}szl\'{o} and Black, Timothy J. F. and Wuu, Angela},
  title =	{{List-Decoding Homomorphism Codes with Arbitrary Codomains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.29},
  URN =		{urn:nbn:de:0030-drops-94338},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.29},
  annote =	{Keywords: Error-correcting codes, Local algorithms, Local list-decoding, Finite groups, Homomorphism codes}
}
Document
DOI: 10.4230/DagRep.5.12.1
The Graph Isomorphism Problem (Dagstuhl Seminar 15511)

Authors: László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán

Published in: Dagstuhl Reports, Volume 5, Issue 12 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15511 "The Graph Isomorphism Problem". The goal of the seminar was to bring together researchers working on the numerous topics closely related to the Isomorphism Problem to foster their collaboration. To this end the participants of the seminar included researchers working on the theoretical and practical aspects of isomorphism ranging from the fields of algorithmic group theory, finite model theory, combinatorial optimization to algorithmics. A highlight of the conference was the presentation of a new quasi-polynomial time algorithm for the Graph Isomorphism Problem, providing the first improvement since 1983.
Cite as

László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán. The Graph Isomorphism Problem (Dagstuhl Seminar 15511). In Dagstuhl Reports, Volume 5, Issue 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{babai_et_al:DagRep.5.12.1,
  author =	{Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo},
  title =	{{The Graph Isomorphism Problem (Dagstuhl Seminar 15511)}},
  pages =	{1--17},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{12},
  editor =	{Babai, L\'{a}szl\'{o} and Dawar, Anuj and Schweitzer, Pascal and Tor\'{a}n, Jacobo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.5.12.1},
  URN =		{urn:nbn:de:0030-drops-58028},
  doi =		{10.4230/DagRep.5.12.1},
  annote =	{Keywords: canonical forms, complexity, computational group theory, graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.453
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers

Authors: László Babai and Youming Qiao

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n^{log n} bound on the time complexity for the general case has not been improved over the past four decades. Recently, Babai et al. (following Babai et al. in SODA 2011) presented a polynomial-time algorithm for groups without abelian normal subgroups, which suggests solvable groups as the hard case for group isomorphism problem. Extending recent work by Le Gall (STACS 2009) and Qiao et al. (STACS 2011), in this paper we design a polynomial-time algorithm to test isomorphism for the largest class of solvable groups yet, namely groups with abelian Sylow towers, defined as follows. A group G is said to possess a Sylow tower, if there exists a normal series where each quotient is isomorphic to Sylow subgroup of G. A group has an abelian Sylow tower if it has a Sylow tower and all its Sylow subgroups are abelian. In fact, we are able to compute the coset of isomorphisms of groups formed as coprime extensions of an abelian group, by a group whose automorphism group is known. The mathematical tools required include representation theory, Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980 work on p'-automorphisms of abelian p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized versin of the graph-isomorphism-hard setwise stabilizer problem, which may be of independent interest.
Cite as

László Babai and Youming Qiao. Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 453-464, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.STACS.2012.453,
  author =	{Babai, L\'{a}szl\'{o} and Qiao, Youming},
  title =	{{Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{453--464},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.453},
  URN =		{urn:nbn:de:0030-drops-34008},
  doi =		{10.4230/LIPIcs.STACS.2012.453},
  annote =	{Keywords: polynomial-time algorithm, group isomorphism, solvable group}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2445
Evasiveness and the Distribution of Prime Numbers

Authors: László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$. We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-\epsilon})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of ``forbidden subgraph $H$'' is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.
Cite as

László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the Distribution of Prime Numbers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.STACS.2010.2445,
  author =	{Babai, L\'{a}szl\'{o} and Banerjee, Anandam and Kulkarni, Raghav and Naik, Vipul},
  title =	{{Evasiveness and the Distribution of Prime Numbers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{71--82},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2445},
  URN =		{urn:nbn:de:0030-drops-24451},
  doi =		{10.4230/LIPIcs.STACS.2010.2445},
  annote =	{Keywords: Decision tree complexity, evasiveness, graph property, group action, Dirichlet primes, Extended Riemann Hypothesis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact